package java_algorithm;

import java.util.Arrays;

public class demo003 {

    public static void main(String[] arge){

        System.out.println(new ShellSort().sort(new int[]{7,3,4,6,8}));
    }

    public static class ShellSort {
        public int[] sort(int[] sourceArray){
            // 对 arr 进行拷贝，不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

            int gap = 1;
            while (gap < arr.length) {
                gap = gap * 3 + 1;
            }

            while (gap > 0) {
                for (int i = gap; i < arr.length; i++) {
                    int tmp = arr[i];
                    int j = i - gap;
                    while (j >= 0 && arr[j] > tmp) {
                        arr[j + gap] = arr[j];
                        j -= gap;
                    }
                    arr[j + gap] = tmp;
                }
                gap = (int) Math.floor(gap / 3);
            }

            return arr;
        }
    }
}
